package middle;

import java.util.Stack;

/**
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ReverseWordsInAString {
    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        solution1.reverseWords("  hello world  ");
    }

    /**
     * 倒过来输出，这种很容易联想到数据结构——栈
     * */
    class Solution {
        public String reverseWords(String s) {
            Stack<String> stack = new Stack<>();
            int start = -1;
            for (int i = 0; i < s.length(); i++) {
                if(s.charAt(i) == ' ' && start != -1){
                    stack.push(s.substring(start,i));
                    start = -1;
                }
                if(s.charAt(i) != ' ' && start == -1){
                    start = i;
                }
            }
            if(start != -1){
                stack.push(s.substring(start));
            }
            StringBuilder stringBuilder = new StringBuilder();
            while(!stack.isEmpty()){
                stringBuilder.append(stack.pop()).append(" ");
            }
            return stringBuilder.toString().trim();
        }
    }

    /**
     * 超过100%的解法
     * 用一个数组赋值
     * */
    static class Solution1 {
        public String reverseWords(String s) {
            int len = s.length();
            char[] chars = new char[len+1];
            int newPos = 0;
            int pos = len-1;
            while(pos >= 0){
                // 找到一个单词的结尾位置
                while (pos >= 0 && s.charAt(pos) == ' ') pos--;
                int right = pos;
                // 找到一个单词的开始位置
                while (pos >= 0 && s.charAt(pos) != ' ') pos--;
                int left = pos + 1;
                // 将一个单词放入到结果数组中
                while(left <= right){
                    chars[newPos++] = s.charAt(left);
                    if(left == right){
                        chars[newPos++] = ' ';
                    }
                    left++;
                }
            }
            return newPos == 0 ? "" : new String(chars, 0, newPos-1);
        }
    }
}
